package java;

public class Question25 {
    public static void main(String[] args) {

        ListNode root = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        root.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode current = root;
        while (current != null){
            System.out.println(current.val);
            current = current.next;
        }
        ListNode head = reverseKGroup(root,2);
        System.out.println("===============");
        current = head;
        while (current != null){
            System.out.println(current.val);
            current = current.next;
        }
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null){
            return null;
        }
        if (k < 2){
            return head;
        }
        ListNode start = head;
        ListNode current = head;
        ListNode before = head;
        ListNode lastTail = null;
        ListNode end = getNextKth(start,k);
        head = end;
        while (end != null){
            current = current.next;
            while (current != end){
                before.next = current.next;
                current.next = start;
                start = current;
                current = before.next;
                if (lastTail != null){
                    lastTail.next = start;
                }
            }

            before.next = current.next;
            current.next = start;
            if (lastTail != null){
                lastTail.next = current;
            }
            lastTail = before;
            start = before.next;
            current = before.next;
            before = before.next;
            end = getNextKth(start,k);
        }
        return head;
    }

    private static ListNode getNextKth(ListNode start, int k) {
        if (start == null){
            return null;
        }
        for (int i = 0; i < k - 1 ; i ++){
            if (start.next == null){
                return null;
            }
            start = start.next;
        }
        return start;
    }

}
